package leetcode.year2021;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class _02FilterNum {
  // 整型数组，找到所有满足以下条件的数 : 左边的值全部小于本身，右边的值全部大于本身,返回结果数组
  // 时间复杂度需要满足 O（N）
  public static void main(String[] args) {
    int[] nums = {1,2,4,3,9,5,6,10};
    int[] ans = filterNum(nums);
    for (int i = 0; i < ans.length; i++) {
      System.out.print(ans[i] + ",");
    }
  }

  public static int[] filterNum(int[] nums){
    int length = nums.length;
    // 使用数组记录左边最大的数
    int[] leftMax = new int[length];
    leftMax[0] = Integer.MIN_VALUE;

    for (int i = 1; i < length; i++) {
      leftMax[i] = Math.max(leftMax[i-1],nums[i-1]);
    }
    // 使用数组记录右边最小的数
    int[] rightMin = new int[length];
    rightMin[length-1] = Integer.MAX_VALUE;
    for (int i = length-2; i >= 0 ; i--) {
      rightMin[i] = Math.min(rightMin[i + 1], nums[i + 1]);
    }

    // 逐个遍历判断是否符合要求
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < length; i++) {
      if (nums[i] > leftMax[i] && nums[i] < rightMin[i]){
        ans.add(nums[i]);
      }
    }
    return ans.stream().mapToInt(t -> t).toArray();
  }

}
